package com.xinxin.leetcode.problem671;

import com.xinxin.leetcode.common.CommonUtil;
import com.xinxin.leetcode.common.TreeNode;
import com.xinxin.leetcode.common.TreeUtil;

/**
 * @author ShiXinXin
 * @date 2020-02-18 23:19
 */
public class Solution {
    public int findSecondMinimumValue(TreeNode root) {
        if (root == null || root.left == null) {
            return -1;
        }
        if (root.left.val > root.val && root.right.val > root.val) {
            return Math.min(root.left.val, root.right.val);
        }
        if (root.left.val > root.val) {
            int v = findSecondMinimumValue(root.right);
            if (v == -1) {
                return root.left.val;
            }
            return Math.min(root.left.val, v);
        }
        if (root.right.val > root.val) {
            int v = findSecondMinimumValue(root.left);
            if (v == -1) {
                return root.right.val;
            }
            return Math.min(root.right.val, v);
        }
        int vl = findSecondMinimumValue(root.left);
        int vr = findSecondMinimumValue(root.right);
        if (vl == -1) {
            return vr;
        }
        if (vr == -1) {
            return vl;
        }
        return Math.min(vr, vl);
    }

    public static void main(String[] args) {
        TreeNode root = TreeUtil.createTree(CommonUtil.createArr(2, 2, 0, 0, 5, 5, 0, 0, 7, 0, 0));
        System.out.println(new Solution().findSecondMinimumValue(root));
    }
}
